<?php
/**
 * @title 309. 最佳买卖股票时机含冷冻期 - 迭代
 * @author start2004
 */


class Solution {

    /**
     * @param Integer[] $prices
     * @return Integer
     */
    function maxProfit($prices) {
        /**
         * @since 2020-07-10 排除特殊情况
         */
        $len = count($prices);
        if($len <= 1){
            return 0;
        } else {}

        /**
         * @since 2020-07-10 每次递归结果缓存起来, 避免反复计算
         */
        $dp = [
            "-2" => 0,
            "-1" => 0,
            "0" => 0,
            "1" => 0,
        ];

        /**
         * @since 2020-07-10 循环计算dp(1)到dp(len-1)
         */
        for($i=1; $i<$len; $i++){
            /**
             * @since 2020-07-10 第i天不操作, 等于dp(i-1)
             */
            $max = $dp[$i-1];

            /**
             * @since 2020-07-10 循环第i天是`卖`操作, 对应操作的`买`应是第0天到第i-1天
             */
            for ($j=0; $j<=$i-1; $j++){
                $max = max($max, $prices[$i]-$prices[$j] + $dp[$j-2]);
            }

            /**
             * @since 2020-07-10 赋值
             */
            $dp[$i] = $max;
        }

        /**
         * @return
         */
        return $dp[$len-1];
    }
}




/**
 * @url http://127.0.0.1/leetcode/202007/2020.07.10_2.php
 */
$datas = [
    [1,2,3,0,2],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->maxProfit($data);
    var_dump($result);
    echo str_repeat("<br>", 3);
}
$xhprof->end();
